An electronic signature is a technique for verifying the integrity of electronic documents. To assist in the acceleration of the use or utilization of electronic documents, many needs exist for fetching (extraction) of a portion of a signed electronic document. In general electronic signatures, however, such extraction may lead to tampering with the document, and therefore it is difficult to verify integrity. As techniques to solve this problem, applied techniques of partially extractable electronic signatures, called sanitizable signature and deletable signature techniques, are available. Those techniques even allow verification of the integrity of a portion that is extracted.
A general electronic signature is defined by using a two-process model: a signing process for performing signing and a verifying process for performing verification. In an extractable signature scheme, on the other hand, as shown in FIG. 1, a three-process model is used: a signing process for performing signing, an extracting process for extracting a portion from a document signed by the signing process, and a verifying process for verifying the extracted document. The signing process signs a document using a certain method. Then, the extracting process receives the signed document and the signature. The extracting process extracts a portion of the received document, and generates extraction information involved in the extraction or updates the signature. Then, the verifying process receives the extracted document as well as the signature and the extraction information. The verifying process verifies, from the extracted document, the signature and the extraction information, that the extracted document is a portion of the document signed by the signing process. A signature scheme fulfilling the flow described above is defined as an extractable signature scheme.
In a sanitizable signature or deletable signature scheme, a document is divided into a plurality of document segments in advance, and the document segments are signed or are partially signed. In a sanitizable signature or deletable signature scheme of the related art, the amount of signature information may increase in proportion to the number of document segments at the time of signing, or an amount of extraction information proportional to the number of document segments to be extracted or to the number of document segments to be deleted may be required during extraction. Therefore, a large amount of signature information or a large amount of extraction information is required to extract a part of a large size document, resulting in significant inefficiency.
One typical sanitizable signature scheme is a signature scheme (hereinafter referred to as “SUMI-4”) disclosed in Japanese Unexamined Patent Application Publication No. 2004-364070. This signature scheme requires only one signature regardless of the number of document segments. However, a group of hash values of document segments to be deleted is required during extraction, and therefore the amount of extraction information increases in proportion to the number of document segments deleted.
This scheme will be described with reference to FIG. 2. At the time of signing, a signing process divides document information M into pieces of document segment information m1 to m4, and adds pieces of document segment ID information ID1 to ID4 to the pieces of document segment information m1 to m4 to generate ID-added document segments M1 to M4. Then, hash values h1 to h4 are calculated. The signing process signs the hash values h1 to h4 (with a signature σ), and forwards ID-added document segments M1 to M4 and the signature σ to an extracting process. During extraction, the extracting process determines an ID-added document segment to be extracted. Here, it is assumed that the ID-added document segment M2 is to be extracted. Then, the extracting process calculates hash values h1, h3, and h4 of the ID-added document segments M1, M3, and M4 to be deleted (not to be extracted), and publishes h1, M2, h3, h4 and the signature σ of the signing process. That is, instead of the ID-added document segments M1, M3, and M4 to be deleted, the hash values h1, h3, and h4 are published. During signature verification, a verifying process calculates a hash value h2 from the published ID-added document segment M2 to recover the hash values h1 to h4 in conjunction with the published hash values h1, h3, and h4 to perform verification using the signature σ. Since the signature σ is a signature added to the hash values h1 to h4 by the signing process, the verifying process can verify that the extracted ID-added document segment M2 is a portion of the document information M signed by the signing process. During extraction, if, instead of an ID-added document segment to be deleted, a hash value thereof is not published, the verifying process is not allowed to perform verification. It is therefore necessary to store an amount of information (hereinafter referred to as “extraction information”) proportional to the number of document segments to be deleted, and a problem occurs in that, as the number of ID-added document segments to be deleted increases, the amount of extraction information to be stored also increases.
Another example of a deletable signature scheme of the related art is a signature scheme (hereinafter referred to as “SUMI-6”) disclosed in Japanese Unexamined Patent Application Publication No. 2006-60722. This signature scheme requires, during signing, partial signatures to be attached to individual document segments and an entire signature which is a superposition of the partial signatures. Thus, a problem occurs in that the amount of signature information increases in proportion to the number of document segments.
A description will be given with reference to FIG. 3. As in FIG. 2, during signing, a signing process divides document information M into pieces of document segment information m1 to m4, and adds pieces of document segment ID information ID1 to ID4 to the pieces of document segment information m1 to m4 to generate ID-added document segments M1 to M4. Then, the signing process calculates hash values h1 to h4, calculates partial signatures σ1 to σ4 using an aggregate signature technique described below, and superimposes the partial signatures σ1 to σ4 to create an entire signature σ. Finally, the signing process forwards the ID-added document segments M1 to M4, the partial signatures σ1 to σ4, and the entire signature σ to an extracting process. During extraction, the extracting process determines an ID-added document segment to be extracted. Here, it is assumed that the ID-added document segment M2 is to be extracted. The extracting process deletes the ID-added document segments M1, M3, and M4 not to be extracted, and utilizes the corresponding partial signatures σ1, σ3, and σ4 to delete information regarding the partial signatures σ1, σ3, and σ4 from the entire signature σ to produce an updated entire signature σ′. Finally, the extracting process publishes the extracted ID-added document segment M2, the partial signature σ2 thereof, and the updated entire signature σ′. During signature verification, a verifying process performs verification using the published ID-added document segment M2 and the updated entire signature σ′. Since the signature σ′ is a signature obtained by deleting information regarding the partial signatures σ1, σ3, and σ4 of the ID-added document segments M1, M3, and M4 deleted by the extracting process from the entire signature σ of the signing process, the verifying process can verify that the extracted ID-added document segment M2 is a portion of the document information M signed by the signing process.
In this scheme, when signing is to be performed, extraction is not performed if partial signature information is not added. It is therefore necessary to store an amount of signature information proportional to the number of document segments to be signed, and a problem occurs in that, as the number of ID-added document segments to be signed increases, the amount of signature information to be stored also increases.
In other words, in sanitizable-signature-based extraction, only one signature (the amount of data is small) is required during signing. During extraction, however, an amount of extraction information corresponding to the number of document segments to be deleted is required in addition to the signature required during signing (the amount of data is large). In deletable-signature-based extraction, a problem arises in that although an extracted document, a signature specific thereto, and an updated entire signature are only required during extraction (the amount of data is small); whereas during signing, an amount of information (specific signature) corresponding to the number of document segments is required in addition to the signature (entire signature) (the amount of data is large).
Another applied technique of electronic signature called aggregate signature technique exists. The aggregate signature technique has attracted attention as a technique capable of reducing the amount of signature data by superimposing signatures in a case where one or a plurality of documents are signed by one or a plurality of signing processes in the distribution of electronic documents or the like.
Typical features of the aggregate signature scheme will now be described. When a plurality of documents are signed by a plurality of persons, if an ordinary electronic signature scheme is employed, as shown in FIG. 4, a number of signature data items corresponding to the number of documents is required. If the aggregate signature scheme is employed, on the other hand, as shown in FIG. 5, signatures of the individual documents can be superimposed (or aggregated) into one signature and the individual documents can be aggregate verified with one signature, and a reduction in the amount of signature data is achieved.
Currently, two aggregate signature construction methods are available: a sequential aggregate signature scheme based on a Rivest-Shamir-Adlema (RSA) signature, which is described in A. Lysyanskaya, et. al., “Sequential Aggregate Signatures from Trapdoor Permutations,” EUROCRYPT 2004, LNCS 3027, pp. 74-90, 2004; and a general aggregate signature scheme based on an elliptic curve cryptosystem called pairing, which is described in D. Boneh, et. al., “Aggregate and Verifiably Encrypted Signatures from Bilinear Maps,” EUROCRYPT 2003, LNCS 2656, pp. 416-432, 2003. The deletable signature scheme described above uses a general aggregate signature scheme.
Japanese Patent No. 2666191 discloses a signature scheme called Schnorr signature scheme in which only portions of a signature can be superimposed. A Schnorr signature is defined as follows.
A prime number p, a generator g thereof, and an order q of the generator g are published as common parameters. A secret-public key pair of a signing process is represented by (sk, pk), where pk=g sk mod p(0<sk<q), and pk is published as a public key of the signing process.
In order to sign a document M to be signed, the signing process generates a random number k (which is kept secret), and a signature σ=(r, s)=(g k mod p, sk×H(r∥M)+k mod q) is calculated, where H(x) denotes a hash value of a value x, and x∥y represents a concatenation of values x and y. During signature verification, a signature is determined to be valid if the value of g s mod p and the value of pk H(r∥M)×r mod p coincide with each other; and a signature is determined to be invalid if they do not coincide with each other.
An superposition of Schnorr signatures will be described with reference to FIG. 6. In the Schnorr signature scheme, a signature value σ is represented by two values such that σ=(r, s). It is assumed that a Schnorr signature on a document A is represented by σA=(rA, sA), and a Schnorr signature on a document B is represented by σB=(rB, sB). In this case, the verification of the document A and the signature σA and the verification of the document B and the signature σB can be individually performed and, in addition, even if s values of each signature are superimposed, the signature can be verified. That is, the signatures of the documents A and B can be verified using the documents A and B and a signature σAB=(rA, rB, sAB), where sAB=sA×sB mod p. Furthermore, signature verification during the superposition determines that a signature is valid if the value of g sAB mod p and the value of pk H(rA∥M)×rA×pk H(rB∥M)×rB mod p coincide with each other; and determine a signature to be invalid if the values do not coincide with each other. In the Schnorr signature scheme, therefore, since s values of a signature can be superimposed, the required amount of signature data can be reduced although the rate of reduction is lower than that of the aggregate signature scheme.
Furthermore, a technique called RSA accumulator is described in J. Benaloh, and M. de Mare, “One-way accumulators: A decentralized alternative to digital signatures,” EUROCRYPT '93, LNCS 765, pp. 274-285, Springer-Verlag, 1994. An RSA accumulator is one type of hash function based on the RSA cryptosystem, and has an superimposition function. The product of two prime numbers p and q, N, is used so as to be used in the RSA cryptosystem. A generator g relatively prime to N and the order φ of the generator g, which is given by φ=LCM(p−1)(q−1), are used. The RSA accumulator has a pseudo-commutative property, which is secure under the RSA assumption. The term “pseudo-commutative” means that if the function f: X×Y→X satisfies the property below in all xεX and all y1 and y2εY, then the function f has a pseudo-commutative property:f(f(x,y1),y2)=f(x,y2),y1)
That is, in a case where the function f is repeatedly applied many times, the function f has a property that the order of application of the function f is changeable (commutative) with respect to the y values. In an RSA accumulator in the document mentioned above, the function f is implemented byfN(x,y)=×H(y)mod N, where H denotes a one-way hash function (such as SHA1).
In the RSA accumulator, the relationship
                                          gH            ⁡                          (                              y                ⁢                                                                  ⁢                1                            )                                ×                      H            ⁡                          (                              y                ⁢                                                                  ⁢                2                            )                                ⁢                                          ⁢          mod          ⁢                                          ⁢          N                =                ⁢                              (                                          gH                ⁡                                  (                                      y                    ⁢                                                                                  ⁢                    1                                    )                                            ⁢                                                          ⁢              mod              ⁢                                                          ⁢              N                        )                    ⁢                      H            (                          y              ⁢                                                          ⁢              2                        )                    ⁢                                          ⁢          mod          ⁢                                          ⁢          N                                        =                ⁢                              (                                          gH                ⁡                                  (                                      y                    ⁢                                                                                  ⁢                    2                                    )                                            ⁢              mod              ⁢                                                          ⁢              N                        )                    ⁢                      H            ⁡                          (                              y                ⁢                                                                  ⁢                1                            )                                ⁢          mod          ⁢                                          ⁢          N                    is established. That is, hash values can be superimposed in random order. In addition, since the RSA accumulator has a one-way property, it is difficult to calculate x values from (g H(y) mod N), H(y), and N (RSA assumption).